package previous.Test_0305;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //最大子数组和
    //状态表示
    //dp[i]:表示在i位置连续子数组的和最大
    //状态转移表示：
    //dp[i]=dp[i-1]+nums[i];
    public int maxSubArray(int[] nums) {
           int n=nums.length;
           int[] dp=new int[n];
           if(n==1) return nums[0];
           dp[0]=nums[0];
           int ret=Integer.MIN_VALUE;
        for (int i = 1; i <n ; i++) {
            //如果都是负数，那就是返回最大的负数，如果是正数都是越加越大
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            ret=Math.max(ret,dp[i]);
        }
        return ret;
    }
    //环形子数组的最大和
    //思路：1.求连续的最大
    //     2.求环形的最大，也就是求连续的最小
    //     3.比较，取最大
    //状态表示：
    //f[i]：表示以i结尾的最大连续数组；
    //g[i]: 表示以i结尾的最小连续数组
    public int maxSubarraySumCircular(int[] nums) {
        int n=nums.length;
        int[] f=new int[n];
        int[] g=new int[n];
        if(n==1) return nums[0];
        f[0]=nums[0];
        g[0]=nums[0];
        int ret1=nums[0];
        int ret2=nums[0];
        int sum=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        for (int i = 1; i < n; i++) {
            f[i]=Math.max(nums[i],f[i-1]+nums[i]);
            ret1=Math.max(f[i],ret1);
            g[i]=Math.min(nums[i],g[i-1]+nums[i]);
            ret2=Math.min(g[i],ret2);
        }
        if(sum-ret2==0) return ret1;
        return Math.max(ret1,sum-ret2);
    }
    //乘积最大子数组
    //状态表示
    //dp[i]:表示以i结尾的最大的乘积连续数组
    //因为乘积有正有父，所以要两个数组
    //状态转移方程：
    //f[i]=Math.max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i]);
    //g[i]=Math.min(nums[i],f[i-1]*nums[i],g[i-1]*nums[i]);
    public int maxProduct(int[] nums) {
        int n=nums.length;
        int[] f=new int[n];
        int[] g=new int[n];
        if(n==1) return nums[0];
        f[0]=nums[0];
        g[0]=nums[0];
        int ret1=nums[0];
        int ret2=nums[0];
        for (int i = 1; i < n ; i++) {
            f[i]=Math.max(nums[i],Math.max(f[i-1]*nums[i],g[i-1]*nums[i]));
            ret1=Math.max(f[i],ret1);
            g[i]=Math.min(nums[i],Math.min(f[i-1]*nums[i],g[i-1]*nums[i]));
            ret2=Math.min(g[i],ret2);
        }
        return ret1;
    }
    //乘积为正数的最长子数组长度
    //f[i]:表示以i结尾的最长乘积为正数的长度
    //g[i]:表示以i结尾的最长乘积为负数的长度
    //状态转移方程
    //大于0 f[i]=f[i-1]+1;
    //小于0 g[i]=g[i-1]+1;
    public int getMaxLen(int[] nums) {
        int n=nums.length;
        int[] f=new int[n+1];
        int[] g=new int[n+1];
        int ret=Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if(nums[i-1]>0){
                f[i]=f[i-1]+1;
                g[i]=g[i-1]==0? 0:g[i-1]+1;
            }else if(nums[i-1]<0){
                f[i]=g[i-1]==0? 0:g[i-1]+1;
                g[i]=f[i-1]+1;
            }
            ret=Math.max(ret,f[i]);
        }
        return ret;
    }
}
